#pragma once
#include<iostream>
#include<string>
#include<algorithm>
template<class K,class V>
class BSTreeNode
{
public:
	BSTreeNode(K key = 0, V value = 0):_key(key),_value(value){}
public:
	K _key;
	V _value;
	BSTreeNode* _left=nullptr;
	BSTreeNode* _right=nullptr;
};


template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K, V> Node;
public:
	bool Insert(const K& key, const V& value)
	{
		if (_root == nullptr)
		{
			_root = new Node(key, value);
		}
		else
		{
			Node* parent = _root;
			Node* child = _root;
			while (child)
			{
				if (key < child->_key)
				{
					parent = child;
					child = parent->_left;
				}
				else if(key>child->_key)
				{
					parent = child;
					child = parent->_right;
				}
				else
				{
					return false;
				}
			}
			
			child = new Node(key, value);
			if (key < parent->_key)
			{
				parent->_left = child;
			}
			else if(key>parent->_key)
			{
				parent->_right = child;
			}
		}
		return true;
	}
	Node* Find(const K& key)
	{
		Node* parent = _root;
		Node* child = _root;
		while (child)
		{
			if (key < child->_key)
			{
				parent = child;
				child = parent->_left;
			}
			else if (key > child->_key)
			{
				parent = child;
				child = parent->_right;
			}
			else
			{
				return child;
			}
		}
		return nullptr;
	}
	bool Erase(const K& key)
	{
		Node* parent = _root;
		Node* child = parent;
		while (child)
		{
			if (key < child->_key)
			{
				parent = child;
				child = parent->_left;
			}
			else if (key > child->_key)
			{
				parent = child;
				child = parent->_right;
			}
			else
			{
				if (child->_left == nullptr )
				{
					if (child == _root)
					{
						_root = _root->_right;
						delete child;
						return true;
					}
					if (child->_key < parent->_key)
					{
						parent->_left = child->_right;
						delete child;
					}
					else if (child->_key > parent->_key)
					{
						parent->_right = child->_right;
						delete child;
					}
				}
				else if (child->_right == nullptr)
				{
					if (child == _root)
					{
						_root = _root->_left;
						delete child;
						return true;
					}
					if (child->_key < parent->_key)
					{
						parent->_left = child->_left;
						delete child;
					}
					else if (child->_key > parent->_key)
					{
						parent->_right = child->_left;
						delete child;
					}
				}
				else
				{
					Node* max = child->_left;
					Node* maxparent = child;
					while (max->_right)
					{
						maxparent = max;
						max = max->_right;
					}
					std::swap(max->_value, child->_value);
					if (maxparent->_left == max)
						parent->_left = nullptr;
					else
						parent->_right = nullptr;
					delete max;
				}
				return true;
			}
		}
		return false;
	}
	void _InOrder(Node* root)
	{
		if (root==nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		std::cout << root->_value << " ";
		_InOrder(root->_right);
		
	}
	void InOrder()
	{
		Node* root = _root;
		_InOrder(root);
	}
private:
	Node* _root = nullptr;
};

